/**
 * 计数排序
 */
public class CountingSort {

    // 尝试实现通用的计数排序算法
    // indexFn 是映射函数，用来将待排序数组中的元素映射到一个非负整数索引
    // public void sort(int[] nums, Function<Integer, Integer> indexFn) {
    //     // 找到最大索引值
    //     int max = 0;
    //     for (int num : nums) {
    //         int index = indexFn.apply(num);
    //         max = Math.max(max, index);
    //     }
    //
    //     // 按照最大索引值决定count数组的大小
    //     // 统计每个元素出现的次数
    //     int[] count = new int[max + 1];
    //     for (int num : nums) {
    //         int index = indexFn.apply(num);
    //         count[index]++;
    //     }
    //
    //     // 累加count数组，得到的是indexFn(nums[i])在排序后的数组中结束位置
    //     for (int i = 1; i < count.length; i++) {
    //         count[i] += count[i - 1];
    //     }
    //
    //     // 根据每个元素排序后的索引位置，完成排序
    //     // 这里注意，我们从后往前遍历nums，是为了保证排序的稳定性
    //     int[] sorted = new int[nums.length];
    //     for (int i = nums.length - 1; i >= 0; i--) {
    //         int index = indexFn.apply(nums[i]);
    //         sorted[count[index] - 1] = nums[i];
    //         count[index]--;
    //     }
    //     // 把排序结果复制回原数组
    //     for (int i = 0; i < nums.length; i++) {
    //         nums[i] = sorted[i];
    //     }
    // }

    // 做算法时使用
    public void sort(int[] nums) {
        // 找到最大值和最小值
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        // 计算索引偏移量和count数组大小
        for (int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }

        // 根据最大值和最小值，将元素映射到从0开始的索引值
        int offset = -min;
        int[] count = new int[max - min + 1];;
        // 统计每个元素出现的次数
        for (int num : nums) {
            count[num + offset]++;
        }
        // 累加count数组，得到的是nums[i]在排序后的数组中结束的位置
        for (int i = 1; i < count.length; i++) {
            count[i] += count[i - 1];
        }

        // 根据每个元素排序后的索引位置，完成排序
        // 从后往前遍历，保证稳定性
        int[] sorted = new int[nums.length];
        for (int i = nums.length - 1; i >= 0; i--) {
            sorted[count[nums[i] + offset] -1] = nums[i];
            count[nums[i] + offset]--;
        }

        // 把排序结果复制回原数组
        for (int i = 0; i < nums.length; i++) {
            nums[i] = sorted[i];
        }
    }
}
